package demo01;

import java.util.Random;

//数组最小前k个数(快速选择算法)
class Solution {
    public int[] smallestK(int[] arr, int k) {
        int l = 0,r = arr.length-1;
        qsort(arr,l,r,k);
        int[] ret = new int[k];
        for(int i = 0;i<k;i++){
            ret[i] = arr[i];
        }
        return ret;
    }
    public void qsort(int[] nums,int l,int r,int k){
        if(l>r) return;
        int n = new Random().nextInt(r-l+1)+l;
        int key = nums[n];
        int left = l-1,right = r+1, i=l;
        while(i<right){
            if(key>nums[i]) swap(nums,++left,i++);
            else if(key == nums[i]) i++;
            else swap(nums,--right,i);
        }
        int a = left - l + 1,b = right - left - 1;
        if(a>k) qsort(nums,l,left,k);
        else if((a + b >= k)) return;
        else qsort(nums,right,r,(k - a - b));
    }
    public void swap(int[] nums,int left,int right){
        int t = nums[left];
        nums[left] = nums[right];
        nums[right] = t;
    }

}